class Solution {
    public static void main(String[] args) {
        int[] arr = {200,3,140,20,10} ;
        System.out.println(rob(arr));
    }
    public static int rob(int[] nums) {
        if(nums == null || nums.length == 0) return 0 ; 
        if(nums.length == 1 ) return nums[0] ; 
        int len = nums.length ;
        int[] dp = new int[len+1] ; 
         dp[1] = nums[0] ; 
         dp[2] = nums[1] ;
         for(int i = 2 ; i < len ; i ++){
             dp[i+1] =  nums[i] + Math.max(dp[i-1] , dp[i-2]) ;
         }
             if(len >= 3)
            dp[len] -= dp[1] ; 
          


         return Math.max(dp[len] , dp[len-1]) ; 

    }
}


//class Solution {
//    public int massage(int[] nums) {
//        if(nums == null || nums.length == 0) return 0  ;
//        int len = nums.length ;
//        int[] fdp = new int[len] ;
//        int[] gdp = new int[len] ;
//        fdp[0] = nums[0] ;
//
//        for(int i=1 ; i < len ; i ++){
//            fdp[i] = nums[i] + gdp[i-1] ;
//            gdp[i] = Math.max(gdp[i-1] , fdp[i-1]) ;
//        }
//        return Math.max(fdp[len-1] , gdp[len-1]) ;
//    }
//}